数据结构

转载自：https://blog.csdn.net/zwx19921215/article/details/84303646

数组的定义

数组是由n(n>1)个具有相同数据类型的数据元素a1...an组成的有序序列，且该序列必须存储在一块地址连续的存储单元中。

1.数组中的数组元素就有相同的数据类型

2.数组是一种随机存取结构，给定一组下标就可以访问与其对应的数据元素。

3.数组中的数据元素个数是固定的。

行向量的一位数组形式

列向量的一位数组形式

数组的两种顺序存储方式

1.行优先顺序（Row Major Order）:将数组元素按行排列，第i+1个行向量紧接着第i个行向量后面。对于二维数组，按行优先顺序存储的线性序列为：

c语言是按行优先顺序存储的。

2.列优先顺序（Column Major Order）：将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，对二维数组，按列优先顺序存储的线性序列位：

设有二维数组A=(aij)mxn ，若每个元素占用的存储单元数为 /（个），LOC[a11]表示元素a11的首地址(也可以用a00表示首地址)，即数组的首地址。

1.以“行优先顺序”存储

(1)第1行中的每个元素对应的（首）地址是：

注：如果下标从0开始：LOC[a1j] = LOC[a11]+j x /

(2)第2行中的每个元素对应的（首）地址是：

注：如果下标从0开始：LOC[a2j] = LOC[a11]+(1xn)x/ + jx/

(3)第m行中的每个元素对应的（首）地址是：

注：如果下标从0开始：LOC[amj] = LOC[a11]+(mxn)x/ + jx/

三维数组中任一元素aijk的（首）地址是：

多维数组推而广之。

2.以“列优先顺序”存储

(1)第1列中的每个元素对应的（首）地址是：

(2)第2列中的每个元素对应的（首）地址是：

(3)第n列中的每个元素对应的（首）地址是：

特殊矩阵的压缩存储

特殊矩阵：是指非零元素或零元素的分布有一定规律的矩阵

对于高阶矩阵，若其中非零元素呈现某种规律分布或者矩阵中有大量的零元素，若仍然用常规方法存储，可能存储重复的非零元素或零元素，将造成存储空间的大量浪费。对这类矩阵进行压缩存储。

1.多个相同得非零元素只分配一个存储空间

2.零元素不分配空间

比如：一个nxn的二阶矩阵压缩成一个n的一维空间，大大减少了存储空间，即压缩存储。

1.对称矩阵

若一个n阶方阵A=(aij)nxn中的元素满足aij=aji ，i>=1，j=j：aij 在下三角形中，直接保存在sa中。aij之前的i-1行共有元素个数:1+2+....+(i-1) = i(i-1)/2，在第i行上，aij之前恰有j-1个元素，因此，元素aij保存在向量sa中时的下标值k之间的对应关系是:

k=i x (i-1) /2 + j-1      (i>=j)

若i